//
// Created by DengLibin on 2018/12/16 0016.
//

#include <iostream>
#include <vector>
#include <string>
using namespace std;
//KMP算法
// next[i]（i从0开始算）代表着，除去第i个数，在一个字符串里面从第一个数到第（i-1）字符串前缀与后缀最长重复的个数。
//计算next数组
vector<int>* getNextArray(const string& ptr)
{
    int prtLen = ptr.length();//模板字符串的长度
    vector<int>* next = new vector<int>(prtLen,0);//动态数组
    int index=0, len=0;//index:模版字符串下标；len:最大相同前后缀长度


    next->at(0)=0; //模版字符串的第一个字符的最大相同前后缀长度为0

    //初始条件 index 从0 递增到 1 ,此时len还是0,计算len,然后赋值 next[index]=len
    for (index = 1, len = 0; index < prtLen; ++index)
    {

        while (len > 0 && ptr[index] != ptr[len])
        {

            len = *(next->begin() + (len - 1));
        }
        if (ptr[index] == ptr[len])
        {
            len++;
        }
        *(next->begin() + index) = len;
    }

    return next;
}

int kmp(string & tpr, string &ptr)
{

    int tLen = tpr.length();
    int pLen = ptr.length();
    vector<int> * pVector = getNextArray(ptr);

    int i, q; //i 源串的下标 q:模式串的下标
    for (i = 0, q = 0; i < tLen; ++i)
    {
        while (q > 0 && ptr[q] != tpr[i])
        {
            q = *(pVector->begin() + (q - 1));
        }
        if (ptr[q] == tpr[i])
        {
            q++;
        }
        if (q == pLen)
        {
            break;
        }
    }
    delete pVector;
    return (i - pLen + 1);

}

int main39(int argc, char * argv[])
{
    string tpr = "helloworld";
    string ptr = "world";
    cout << kmp(tpr,ptr) << endl;
    return 0;
}